package 二叉树;

import lombok.val;

import java.util.ArrayList;
import java.util.List;

public class No99恢复二叉搜索树 {

    /**
     * 给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。
     * 进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗？
     *
     * 示例 1：
     * 输入：root = [1,3,null,null,2]
     * 输出：[3,1,null,null,2]
     * 解释：3 不能是 1 左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。
     * 示例 2：
     * 输入：root = [3,1,4,null,null,2]
     * 输出：[2,1,4,null,null,3]
     * 解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。
     *  
     * 提示：
     * 树上节点的数目在范围 [2, 1000] 内
     * -231 <= Node.val <= 231 - 1
     */

    private TreeNode lastNode;
    private TreeNode r1;
    private TreeNode r2;

    //中序遍历,无需minValue和maxValue的困扰
    public void recoverTreeGood(TreeNode root) {

        midGo(root);

        int tempR1=r1.val;
        r1.val=r2.val;
        r2.val=tempR1;

    }

    private void midGo(TreeNode node) {

        if(node==null){
            return;
        }

        midGo(node.left);

        if(lastNode==null){
            lastNode=node;//最小元素
        }else{

            if(lastNode.val>node.val){
                //当前元素小于前一位元素,不符合升序
                if(r1==null) {
                    r1 = lastNode;
                    r2 = node;
                }else{
                    //有两个了
                    r2 = node;
                }
            }

            lastNode=node;//更新上一位元素

        }

        midGo(node.right);

    }

    public static void main(String[] args) {
//        No99恢复二叉搜索树 n=new No99恢复二叉搜索树();
//        TreeNode treeNode = TreeNode.getNodeByArr(new Integer[]{1,3,null,null,2});
//        n.recoverTreeGood(treeNode);
//        treeNode.printNode();
        System.out.println(1<<1);
    }

}
